#include <iostream>

using namespace std;
/*
m<n 
fun(m,n) =  fun(m,m) 
m>=n
fun(m,n) = 放满fun(m-n,n) + 有空盘 fun(m,n-1)

n==1  1
m==0 || m==1   1
*/ 

int apple(int m,int n){
	if(m==0||m==1||n==1) return 1;
	if(m>=n) return apple(m-n,n)+apple(m,n-1);
	if(m<n) return apple(m,m);
}

int main(){
	int t,m,n;
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>m>>n;
		cout<<apple(m,n)<<endl;
	}
    return 0;
}
